import java.util.*;

//最长有效括号
public class LongestBracket {
}
class LongestBracketSolution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack();
        List<Integer> list = new ArrayList();
        char[] chas = s.toCharArray();
        int n = chas.length;
        for(int i=0;i<n;i++){
            if(!stack.isEmpty()&&chas[stack.peek()]=='('&&chas[i]==')'){
                list.add(stack.pop());
                list.add(i);
            }else stack.push(i);
        }
        int len = 0;
        if(list.size()==0)return 0;
        int end = list.get(list.size()-1);
        int start = list.get(list.size()-2);
        len = end-start+1;
        for(int i=list.size()-3;i>0;){
            if(list.get(i)<end&&list.get(i)>start)i-=2;
            else if(list.get(i)==start-1){
                start = list.get(i-1);
                len = Math.max(len,end-start+1);
                i-=2;
            }
            else{
                end = list.get(i);
                start = list.get(i-1);
                i-=2;
                len = Math.max(end-start+1,len);
            }
        }
        return len;
    }
}
